// Copyright 2012 The go-algs Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package hash implements functions for the creation and manipulation of an
// array based hash table using open addressing and double hashing..  For more
// documentation on this data structure please see chapter 11 of CLRS 2nd
// edition.
package hash

import (
	"errors"
	"math"
)

const (
	A1 = math.Phi - 1 // Constant based on the golden ratio
	A2 = math.Pi - 3  // Constant based on Pi
)

// You should not cast from an existing array with data to a hash table.
type Hash []int

// Allocates memory for the hash table and initializes all the spots to -1 or
// empty.
func NewHash(n int) Hash {
	h := make(Hash, n)
	for i := range h {
		h[i] = -1
	}
	return h
}

// The hash function returns an index into the array based on the hash of the
// provided key.  Here we make use of double hashing (CLRS 11.4) and the
// multiplication method (CLRS 11.3.2).
func (h Hash) hash(k, i int) int {
	m := float64(len(h))
	fk := float64(k)
	fi := float64(i)
	h1 := m * math.Mod(fk*A1, 1)
	h2 := m * math.Mod(fk*A2, 1)
	return int(math.Mod(h1+fi*h2, m))
}

// Insert places a key into the hash table using open-addressing (CLRS 11.4).
func (h Hash) Insert(k int) (int, error) {
	for i := range h {
		s := h.hash(k, i)
		if h[s] < 0 {
			h[s] = k
			return s, nil
		}
	}
	return -1, errors.New("full")
}

// Find finds a key in the hash table using open-addressing (CLRS 11.4).
func (h Hash) Find(k int) (int, error) {
	for i := range h {
		s := h.hash(k, i)
		if h[s] == -1 {
			break
		}
		if h[s] == k {
			return s, nil
		}
	}
	return -1, errors.New("not found")
}

// Delete removes an item from the hash table and uses -2 as distinct from -1
// so that existing lookup chains are not broken.
func (h Hash) Delete(k int) error {
	for i := range h {
		s := h.hash(k, i)
		if h[s] == -1 {
			break
		}
		if h[s] == k {
			h[s] = -2
			return nil
		}
	}
	return errors.New("not found")
}
